//给定一个二叉树，判断它是否是高度平衡的二叉树。 
//
// 本题中，一棵高度平衡二叉树定义为： 
//
// 
// 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [3,9,20,null,null,15,7]
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：root = [1,2,2,3,3,null,null,4,4]
//输出：false
// 
//
// 示例 3： 
//
// 
//输入：root = []
//输出：true
// 
//
// 
//
// 提示： 
//
// 
// 树中的节点数在范围 [0, 5000] 内 
// -10⁴ <= Node.val <= 10⁴ 
// 
// Related Topics 树 深度优先搜索 二叉树 👍 954 👎 0

package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class BalancedBinaryTree {
    public static void main(String[] args) {
        Solution solution = new BalancedBinaryTree().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        /**
         * 后序递归法
         * @param root
         * @return
         */
        /*
        public boolean isBalanced(TreeNode root) {
            return getHeight(root) == -1 ? false : true;
        }

        // -1表示此时高度差已经大于1
        public int getHeight(TreeNode root) {
            if (root == null) {
                return 0;
            }

            int leftHeight = getHeight(root.left);  // 左
            if (leftHeight == -1) return -1;
            int rightHeight = getHeight(root.right);// 右
            if (rightHeight == -1) return -1;
            if (Math.abs(leftHeight - rightHeight) > 1) {   // 中
                return -1;  // 左右子树高度相差大于1，返回-1
            } else {
                return 1 + Math.max(leftHeight, rightHeight); // 左右子树高度相差小于1，此节点作为根节点的高度就为最大深度
            }
        }
        */

        // 后序简洁版
        public boolean isBalanced(TreeNode root) {
            if (root == null) return true;
            return getDepth(root) == -1 ? false : true;
        }

        public int getDepth(TreeNode root) {
            if (root == null) return 0;
            int left = getDepth(root.left);
            int right = getDepth(root.right);

            if (left == -1 || right == -1 || Math.abs(left - right) > 1) return -1;
            else return 1 + Math.max(left, right);
        }

        /**
         * 迭代法（时间复杂度O(n ^ n)）
         *
         * @param root
         * @return
         */
        /*public boolean isBalanced(TreeNode root) {
            if (root == null) return true;
            // 然后再用栈来模拟前序遍历，遍历每一个节点的时候，再去判断左右孩子的高度是否符合
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            int leftHeight = 0, rightHeight = 0;

            while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                leftHeight = getHeight(node.left);
                rightHeight = getHeight(node.right);
                if (Math.abs(leftHeight - rightHeight) > 1) {   // 中
                    return false;
                } else {
                    if (node.right != null) isBalanced(node.right);  // 右（空节点不入栈）
                    if (node.left != null) isBalanced(node.left);  // 左（空节点不入栈）
                }
            }
            return true;
        }*/

        /**
         * 层序求深度
         *
         * @param root
         * @return
         */
        /*public int getHeight(TreeNode root) {
            if (root == null) {
                return 0;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            int height = 0;
            while (!queue.isEmpty()) {
                int len = queue.size();
                height++;

                while (len > 0) {
                    TreeNode node = queue.poll();
                    if (node.left != null) queue.offer(node.left);
                    if (node.right != null) queue.offer(node.right);
                    len--;
                }

            }
            return height;
        }*/

    }
//leetcode submit region end(Prohibit modification and deletion)

}
